Encrypted databases provide data protection (security) in cloud platforms and/or database-as-a-service settings. In encrypted databases, data (plaintext) can be encrypted at the client to provide encrypted data (ciphertext), which can be provided to the database for storage. In some examples, a third-party provides and maintains the database. That is, the database is outsourced to the third-party. For example, a client encrypts data using one or more encryption keys to provide encrypted data, which the client sends to the third-party for storage in the database.
Outsourcing a database offers efficient resource management and low maintenance costs for clients, but exposes outsourced data (client data) to a service provider (the third-party providing the database and its agents). One issue is periodically re-encrypting the database (e.g., changing the encryption key(s)), because it may be difficult to determine whether an encryption key has been compromised and data is at risk. In one traditional approach, the entire database is downloaded, is rekeyed using a different encryption key, and is uploaded back to the database. This download, rekey, and upload implies huge communication costs and often a significant downtime.